CODE 96. Sudoku Solver

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/10/29/2013-10-29-CODE 96 Sudoku Solver/

访问原文「CODE 96. Sudoku Solver」

Write a program to solve a Sudoku puzzle by filling the empty cells.
Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

A sudoku puzzle…

…and its solution numbers marked in red.

private final static char[] nineNumbers = { '1', '2', '3', '4', '5', '6',
			'7', '8', '9' };

	public void solveSudoku(char[][] board) {
		// IMPORTANT: Please reset any member data you declared, as
		// the same Solution instance will be reused for each test case.
		ArrayList<ArrayList<Character>> cols = new ArrayList<ArrayList<Character>>();
		ArrayList<ArrayList<Character>> rows = new ArrayList<ArrayList<Character>>();
		ArrayList<Integer> indexes = new ArrayList<Integer>();

		for (int i = 0; i < 9; i++) {
			ArrayList<Character> row = new ArrayList<Character>();
			for (int j = 0; j < 9; j++) {
				row.add(board[i][j]);
				if (board[i][j] == '.') {
					int index = j + i * 9;
					indexes.add(index);
				}
			}
			rows.add(row);
		}
		for (int i = 0; i < 9; i++) {
			ArrayList<Character> col = new ArrayList<Character>();
			for (int j = 0; j < 9; j++) {
				col.add(board[j][i]);
			}
			cols.add(col);
		}
		dfs(cols, rows, indexes, indexes.size(), 0);
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (board[i][j] == '.') {
					board[i][j] = rows.get(i).get(j);
				}
			}
		}
	}

	boolean dfs(ArrayList<ArrayList<Character>> cols,
			ArrayList<ArrayList<Character>> rows, ArrayList<Integer> indexes,
			int indexNumber, int index) {
		if (index >= indexNumber) {
			return true;
		}
		int row = indexes.get(index) / 9;
		int col = indexes.get(index) % 9;

		for (int i = 0; i < nineNumbers.length; i++) {
			if (rows.get(row).contains(nineNumbers[i])
					|| cols.get(col).contains(nineNumbers[i])) {
				continue;
			} else {
				int m = 0;
				int n = 0;
				for (m = 3 * (row / 3); m < 3 * (row / 3 + 1); m++) {
					for (n = 3 * (col / 3); n < 3 * (col / 3 + 1); n++) {
						if (rows.get(m).get(n) == nineNumbers[i]) {
							break;
						}
					}
					if (n < 3 * (col / 3 + 1)) {
						break;
					}
				}
				if (m < 3 * (row / 3 + 1) || n < 3 * (col / 3 + 1)) {
					continue;
				}
			}
			rows.get(row).set(col, nineNumbers[i]);
			cols.get(col).set(row, nineNumbers[i]);
			boolean result = dfs(cols, rows, indexes, indexNumber, index + 1);
			if (result) {
				return true;
			}
			rows.get(row).set(col, '.');
			cols.get(col).set(row, '.');

		}
		return false;
	}